#include <bits/stdc++.h>

using namespace std;

// DI序列的有效排列
// 给定一个长度为n的字符串s，其中s[i]是:
// "D"意味着减少，"I"意味着增加
// 有效排列是对有n+1个在[0,n]范围内的整数的一个排列perm，使得对所有的i：
// 如果 s[i] == 'D'，那么 perm[i] > perm[i+1]
// 如果 s[i] == 'I'，那么 perm[i] < perm[i+1]
// 返回有效排列的perm的数量
// 因为答案可能很大，所以请返回你的答案对10^9+7取余
// 测试链接 : https://leetcode.cn/problems/valid-permutations-for-di-sequence/

class Solution 
{
public:
    // 暴力递归
    int numPermsDISequence1(string s) 
    {
        return f(s, 0, s.size() + 1, s.size() + 1);
    }

	// 猜法很妙！
	// 一共有n个数字，位置范围0~n-1
	// 当前来到i位置，i-1位置的数字已经确定，i位置的数字还没确定
	// i-1位置和i位置的关系，是s[i-1] : D、I
	// 0~i-1范围上是已经使用过的数字，i个
	// 还没有使用过的数字中，比i-1位置的数字小的，有less个
	// 还没有使用过的数字中，比i-1位置的数字大的，有n - i - less个
	// 返回后续还有多少种有效的排列
    int f(string& s, int i, int less, int n)
    {
        int ans = 0;
        if(i == n) return 1;
        else if(i == 0 || s[i - 1] == 'D')
        {
            for(int nextLess = 0; nextLess < less; ++nextLess)
            {
                ans += f(s, i + 1, nextLess, n);
            }
        }
        else
        {
            for(int nextLess = less, k = 1; k <= n - i - less; ++k, ++nextLess)
            {
                ans += f(s, i + 1, nextLess, n);
            }
        }
        return ans;
    }

    // 动态规划
    int numPermsDISequence2(string s) 
    {
        const int MOD = 1e9 + 7;
        int n = s.size() + 1;
        int dp[n + 1][n + 1];
        memset(dp, 0, sizeof dp);
        for(int less = 0; less <= n; ++less) dp[n][less] = 1;

        for(int i = n - 1; i >= 0; --i)
        {
            for(int less = 0; less <= n; ++less)
            {
                if(i == 0 || s[i - 1] == 'D')
                {
                    for(int nextLess = 0; nextLess < less; ++nextLess)
                    {
                        dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % MOD;
                    }
                }
                else
                {
                    for(int nextLess = less, k = 1; k <= n - i - less; ++k, ++nextLess)
                    {
                        dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % MOD;
                    }
                }
            }
        }
        return dp[0][n];
    }

    // 通过观察方法2，得到优化枚举的方法
    int numPermsDISequence3(string s) 
    {
        const int MOD = 1e9 + 7;
        int n = s.size() + 1;
        int dp[n + 1][n + 1];
        memset(dp, 0, sizeof dp);
        for(int less = 0; less <= n; ++less) dp[n][less] = 1;

        for(int i = n - 1; i >= 0; --i)
        {
            // n = 9, less = 4, i = 3, more = n - i - less = 2
            if(i == 0 || s[i - 1] == 'D')
            {
                // 'D' : dp[i][less]依赖下一行左边每个格子的总和，dp[i][less - 1]
                // 已经包含了dp[i][less]所依赖的一部分值了，再加上dp[i + 1][less - 1]即可
                dp[i][1] = dp[i + 1][0]; // 只依赖下一行左边一列的一个格子
                for(int less = 2; less <= n; ++less)
                {
                    dp[i][less] = (dp[i][less - 1] + dp[i + 1][less - 1]) % MOD;
                }
            }
            else
            {
                // 'I' : dp[i][less]依赖下一行右边每个各自的总和，而dp[i][less + 1]
                // 已经包含了dp[i][less]所依赖的一部分值了，再加上dp[i + 1][less]即可
                // [less, less + more - 1]，more = n - i - less，区间最大值是 n - i - 1
                dp[i][n - i - 1] = dp[i + 1][n - i - 1]; // 只依赖下一行同一列的格子
                for(int less = n - i - 2; less >= 0; --less)
                {
                    dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % MOD;
                }
            }
        }
        return dp[0][n];
    }
};